10.9 Chan’s APSP 演算法

我們今天來介紹一個 O(n^3 / log n) 時間複雜度的 APSP 演算法。

切成條狀的 (min, +)-矩陣乘法

Fredman 在 1976 年觀察到一些有趣的性質。
對於兩個矩陣 A 和 B 來說，我們可以把 A 切成直條 [A1, A2, …, Aq]、把 B 切成橫條 [B1; B2; …; Bq]，然後把計算 A⋆B 的工作變成計算 min{ A1⋆B1, A2⋆B2, …, Aq⋆Bq }。換句話說，只要計算 q=(n/d) 個大小為 n * d 和 d * n 的 (min, +)-矩陣相乘，最後再合併起來就行了。

如果我們能將這個長條狀的矩陣乘法加速(通常需要 n^2 * d 的時間) 到 n^2，我們就能加快 d 倍了！

計算 APSP 的時間和做 (min, +)-矩陣乘法差不多

我們要計算距離矩陣 D，可以透過利用 (min, +)-矩陣乘法對相鄰矩陣重複平方 log n 次，來找出任兩點之間的最短距離。如果計算 (min, +)-矩陣相乘需要 M(n)，那總時間複雜度就是 O(M(n) log n)。在 Aho, Hopcraft, 和 Ullman 於 1987 年撰寫的演算法教科書中，他們展示了一種方法，只要把 (min, +)-矩陣相乘當成黑盒子，就可以在 O(M(n)) 的時間內算出 APSP，不需要額外多一個 log n。

把上面兩個想法合併起來

這篇文章介紹 Timothy Chan 在 2008 年提出利用 「d維向量的支配集」的概念，在 O(n^2 + c^d n^1.38) 做出 n * d 和 d * n 矩陣以 (min, +) 相乘後的結果 (c 是某個常數)。若我們選取 d = log n / log c = O(log n)，那麼我們就得到一個總時間為 O(n^3 / d) = O(n^3 / log n) 的演算法啦！